package com.chenpp.redis.lru;

import java.util.HashMap;

/**
 * @Description
 * @Author chenpp
 * @Date 2019/10/21 17:52
 * 链表插入和删除快，但是查询慢
 * HashMap查询快，构建一个哈希链表
 * 每次key被访问的时候，把被访问到的key移到头节点，这样当添加新节点的时候，直接添加到头
 * 节点，如果缓存已满，直接删除尾节点就可以了
 */
public class LRUCache<K,V> {


    private HashMap<K,Node<K,V>> linkedHashMap;
    private int capacity;
    private DoubleLinkedList linkedList;

    public LRUCache(int capacity){
        this.capacity = capacity;
        linkedList = new DoubleLinkedList();
        linkedHashMap = new HashMap<K, Node<K,V>>();
    }

    public V get(K k){
        if(!linkedHashMap.containsKey(k)){
            return null;
        }
        V val = linkedHashMap.get(k).getValue();
        //使用put方法把对应的Node放入到链表前面
        put(k,val);
        return val;
    }

    public void put(K key,V val){
        Node node = new Node(key,val);
        //如果节点的key本来就存在，则直接移动到头节点
        if(linkedHashMap.containsKey(key)){
            //linkedList.remove(linkedHashMap.get(key));
            node = linkedList.moveToHead(linkedHashMap.get(key));
        }else{
            //如果key不存在，则新增节点到头部
            if(linkedList.size() >= capacity){
                //移除访问时间最远的节点
                Node last = linkedList.removeLast();
                linkedHashMap.remove(last.getKey());
            }
            linkedList.addFirst(node);
        }
        linkedHashMap.put(key,node);
    }




}
